This invention relates generally to password-based generation of secret cryptographic keys. Methods are provided for generating secret cryptographic keys at user computers based on input of user passwords, together with corresponding apparatus and computer programs and key-management applications employing such methods.
Cryptographic keys are used for a variety of purposes on personal user devices such as personal computers, smart phones, tablets and other computer devices. Such keys may be used, for instance, for signing messages, for authenticating the user computer to other devices, or for encryption/decryption of sensitive data stored on the computer. Often the cryptographic key must be secret to the user computer, so that the key is not shared with any other computer which communicates with the user computer. Secure management of such secret keys is problematical. The key should be readily available for the required use but at the same time protected against unauthorised access, e.g. on loss or theft of the user computer. Since users cannot be expected to remember cryptographic keys, use of a secret key stored on a user computer may be subject to input by the user of a valid user password. However, typical user passwords are cryptographically weak and easily guessed by a thief using an efficient offline brute-force attack. Moreover, a user will often use the same or a similar password for other purposes, such as corporate e-mail, so compromise of his password in other contexts can prejudice security of secret keys.
The use of trusted hardware devices, such smart cards or TPM (Trusted Platform Module) chips, has been proposed for secure management of secret keys. However, such devices are not always available and their use adds to expense and system complexity. Other approaches involve dynamic generation of the key at the user computer through communication via a network with one or more servers. The problem of deriving a (strong) cryptographic key from a (weak) password with the help of one or more servers is a well-studied problem in cryptography, e.g. in the context of key-exchange schemes. Key-exchange schemes involving authenticating a user to a server based on a weak password, and subsequently deriving a shared cryptographic key, are discussed in: “Efficient Password-Authenticated Key Exchange Using Human-Memorable Passwords”, Katz et al.,
EUROCRYPT 2001; and “Universally Composable Password-Based Key Exchange”, Canetti et al, EUROCRYPT 2005. In these schemes, the resulting key is shared by both the user computer and server, and if the server is compromised then the user's password is vulnerable to an offline brute-force attack.
Further work addressed the above problem by using a plurality of servers, all of which must be compromised before an attacker can mount an offline brute-force attack against the server. Examples are described in: “Two-Server Password-Only Authenticated Key Exchange”, Katz at al., Applied Cryptography and Network Security 2005; and “Practical yet universally composable two-server password-authenticated secret sharing”, Camenisch et at, ACM CCS 2012, where the user himself chooses a strong cryptographic key which he can retrieve with the help of his password from two servers. Both servers need to be compromised before the user's password is exposed. Also, U.S. Pat. No. 6,829,356 B1 discloses a client-server system for generating a strong secret such as a cryptographic key from a user password and an ephemeral client secret via interaction of the client and a plurality of servers. These include secret-holding servers, which hold respective secrets for use in generating the key, and verification servers to which the client subsequently proves successful generation of the key. U.S. Pat. No. 7,359,507 B2 describes further variations of the foregoing scheme employing expensive integer arithmetic.
Improved password-based key-generation schemes would be highly desirable.